package argo.hot100.recall;

public class Exist {

    public boolean exist(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length];


        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (dfs(board, visited, word, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;

    }

    public boolean dfs(char[][] board, boolean[][] visited, String word, int x, int y, int depth) {

        if (depth >= word.length() || word.charAt(depth) != board[x][y]) {
           return false;
        } else if(depth==word.length()-1) {
            return true;
        }


        visited[x][y] = true;

        boolean result=false;
        if (x - 1 >= 0 && !visited[x - 1][y]) {
            result=dfs(board, visited, word, x - 1, y, depth + 1);
            if(result){
                return true;
            }

        }
        if (y - 1 >= 0 && !visited[x][y - 1]) {
            result=dfs(board, visited, word, x, y - 1, depth + 1);
            if(result){
                return true;
            }

        }
        if (x + 1 < board.length && !visited[x + 1][y]) {
            result=dfs(board, visited, word, x + 1, y, depth + 1);
            if(result){
                return true;
            }

        }
        if (y + 1 < board[0].length && !visited[x][y + 1]) {
            result=dfs(board, visited, word, x, y + 1, depth + 1);
            if(result){
                return true;
            }

        }

        visited[x][y] = false;


        return result;

    }
}
